home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / Think Class Libraries / CDictionary 1.0 / CDictionary.doc < prev    next >
Encoding:
Text File  |  1994-11-30  |  4.2 KB  |  125 lines  |  [TEXT/KAHL]
  1.  
  2. Documentation for CDictionary
  3. -----------------------------
  4.  
  5. A dictionary is a set of Associations. An association is a set of
  6. key/value pairs. You use a dictionary to store and retrieve values
  7. by their keys. Keys are always unique. The typical implementation allows
  8. you to rapidly retrieve values or find out if the dictionary contains
  9. a particular key or value.
  10.  
  11. This dictionary is implemented as a hash table with linear probing. This
  12. is a simple implementation with pretty low overhead but performs less
  13. well than other algorithms, particularly in regard to unsuccessful lookups.
  14.  
  15. Key size is determined when the dictionary is created; within a given instance
  16. all keys must be the same size. Note, however that a key could be a handle or an
  17. object. In this case, the data the keys reference can be variable size. Values
  18. are always 4 bytes. Although values are declared as CObject, in most cases the
  19. dictionary makes no interpretation of the data so it could be a handle, pointer,
  20. or whatever. The exceptions to this are the DisposeItems, DisposeAll methods. 
  21. These assume the values are valid objects.
  22.  
  23. To use a dictionary, you need to provide two functions (not methods!). These
  24. are:
  25.  
  26.  
  27. Mapping function - This is a function declared as:
  28.  
  29.     unsigned long MyMapProc( void *key)
  30.     
  31.     This function takes a pointer to a key and returns an unsigned
  32.     long integer. It maps the values in the domain of your key to 
  33.     integers. For example, if your keys are strings, you might
  34.     add up all the characters in the string. The map function
  35.     doesn't need to produce values constrained to the table
  36.     size. This is handled by the dictionary.
  37.     
  38.     Hash tables live or die by their hash functions. The more
  39.     evenly the hash values are distributed, the better the
  40.     hash table will perform. You should attempt to take the characteristics
  41.     of your data into account when creating the map function.
  42.     
  43. Comparison function - This function is declared as:
  44.  
  45.     Boolean    MyCompareProc( void *key1, void *key2);
  46.     
  47.     This function takes pointers to two keys and returns true
  48.     if they are equal and fals if they are not.
  49.     
  50. Summary of CDictionary Methods
  51. ------------------------------
  52.     
  53. virtual Boolean IDictionary( Int16 keySize, MapProc map, CompareProc compare,
  54.                 Int32 initialSize);    
  55.                 
  56.     Initializes a dictionary. keySize is the size in bytes of the keys.
  57.     map and compare are pointers to your map and comparison functions.
  58.     initialSize is the initial size of the dictionary. You may pass 0
  59.     to get the default minimum size. FALSE (noErr) is returned if
  60.     initialization was successful.
  61.                 
  62. virtual void Dispose( void);
  63.  
  64.     Dispose of the dictionary but not the contents.
  65.     
  66. virtual void DisposeAll( void);
  67.  
  68.     Disposes of the dictionary and all the contents by calling
  69.     DisposeItems.
  70.     
  71. virtual void DisposeItems( void);
  72.  
  73.     Disposes of the contents of the dictionary but not the dictionary
  74.     itself, so when DisposeItems returns the dictionary is empty
  75.     but still usable. A Dispose() message is sent to each value of
  76.     each association.
  77.  
  78. virtual void Add( void *key, CObject *value);
  79.  
  80.     Adds an association to the dictionary. If key already exists then
  81.     the value is replaced with the new value. No dispose message is 
  82.     sent to the old value.
  83.     
  84. virtual void AddAll( CDictionary *aDictionary);
  85.  
  86.     Adds the contents of an existing dictionary to the dictionary.
  87.     
  88. virtual void Remove( void *key);
  89.  
  90.     Removes the association for key if it is present.
  91.  
  92. virtual CObject *Lookup( void *key);
  93.  
  94.     Returns the value associated with key, or 0 (NIL, NULL) if
  95.     not present.
  96.  
  97. virtual Boolean IncludesKey( void *key);
  98.  
  99.     Returns true if key is in the dictionary, else false.
  100.     
  101. virtual Boolean IncludesValue( CObject *anObject);
  102.  
  103.     Returns true if anObject is in the dictionary, else false.
  104.     Note that this requires a linear search of the dictionary.
  105.  
  106. virtual void DoForEach( DictIterator actionProc);
  107.  
  108.     Iterates over all the dictionary entries and calls actionProc
  109.     for each one. actionProc should be declared as:
  110.     
  111.         void actionProc( tAssociationPtr anAssoc);
  112.         
  113. virtual void DoForEach1( DictIterator1 actionProc, Int32 aParam);
  114.  
  115.     Iterates over all the dictionary entries and calls actionProc
  116.     for each one. actionProc should be declared as:
  117.     
  118.         void actionProc( tAssociationPtr anAssoc, Int32 aParam);
  119.  
  120.  
  121. virtual CObject *Copy( void);
  122.  
  123.     Returns a copy of the dictionary
  124.  
  125.